PERMUTATIONS

Tags: #◇Computer Science #◇STT101A #◇Conceptual #◇Permutations

---

◇Overview

A Permutation is an ordered arrangement of objects. Unlike combinations (where only membership in a subset matters), changing the sequence of selected elements in a permutation creates a distinct outcome: $(A, B, C) \ne (C, B, A)$.

◇Key Definitions

• Permutations of All $n$ Distinct Objects: $P(n, n) = n! = n(n-1)(n-2)\cdots 2 \cdot 1$ (with $0! = 1$ by convention).
• $r$-Permutations of $n$ Distinct Objects (Without Replacement):
  $P(n, r) = {}_nP_r = n(n-1)(n-2)\cdots(n-r+1) = \frac{n!}{(n - r)!}, \quad 0 \le r \le n$
• Permutations of $n$ Objects with Indistinguishable Duplicates: $\frac{n!}{n_1! n_2! \cdots n_k!}$.
• Circular Permutations of $n$ Distinct Objects: $(n - 1)!$.

◇Worked Example

Problem: A cybersecurity competition has $10$ finalist teams.

1. In how many ways can 1st, 2nd, and 3rd place trophies be awarded?
   $P(10, 3) = \frac{10!}{(10-3)!} = 10 \times 9 \times 8 = 720$
2. In how many ways can $6$ speakers be scheduled in $6$ consecutive time slots if Speaker A and Speaker B must speak consecutively (back-to-back)?
   • Treat $\{A, B\}$ as a single fused block, giving $5$ units to permute in $5! = 120$ ways, and multiply by $2! = 2$ internal orderings ($AB$ or $BA$): $5! \times 2! = 240$.

◇References & Navigation

• Previous Topic: ◇Counting by Cases
• Next Topic: ◇Combinations
• Related Notes: ◇Fundamental Principle of Counting, ◇Basic Formula of Probability